package 五排序;

/**
 * @Author XuZhuHong
 * @CreateTime 2021/9/15 19:49
 */
public class InsertSort {
    public static void main(String[] args) {
        int i = 10;
        int[] array = new int[i];
        //生成随机排序
        for (int k = 0; k < i; k++) {
            for (int j = 0; j < i; j++) {
                array[j] = (int) (Math.random() * i * 10);
            }

            //原本数组：
            System.out.printf("第%d \t次数组=》", (k + 1));
            for (int i1 : array) {
                System.out.print(i1 + " \t");
            }

            //开始排序
//            insertSort(array);
            insertSort2(array);

            //输出
            System.out.printf("，排序后为=》", (k + 1));
            for (int i1 : array) {
                System.out.print(i1 + " \t");
            }
            System.out.println();
        }

    }

    //插入排序写法2
    private static void insertSort2(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int index = i;
            int value = array[i];

            while (index - 1 >= 0 && value < array[index - 1]) {
                array[index] = array[index - 1];
                index--;
            }
            array[index] = value;
        }
    }

    private static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            //插入的下标就是当前值的前面一个位置
            int insertIndex = i - 1;
            //每次插入的值 就是当前的第几个值
            int insertValue = array[i];
            //开始执行插入操作  其实就是从后面往前面找
            // 如果找到了比待查入值小的元素就跳出去  没有找到 就继续往前面找 并且把当前这个位置的值  往后移动一个
            // 即  array[insertIndex+1]=array[insertIndex]
            //这里因为insertIndex是从i-1开始  所以 insertIndex+1==i  那么就是把前面的值往后面移动了
            for (int j = insertIndex; j >= 0; j--) {
                //如果插入的这个位置的值 比待插入的小 那么就表示改插入到insertIndex的后面
                if (array[insertIndex] < insertValue) {
                    break;
                    //找到位置就跳出去了
                } else {
                    //如果当前的这个位置比 待插入的值大 那么就把这个位置让出来  把这个位置的值 赋值给后面的
                    //因为 最后的insertValue已经保存下来的 所以可以往后面移动
                    array[insertIndex + 1] = array[insertIndex];
                    insertIndex--;
                }
            }
            //insertIndex表示的是当前的 这个下标的数字 比value小 应该插入在他的后面  所以要 +1
            array[insertIndex + 1] = insertValue;


        }
    }
}
